三国游戏

题目 三国游戏

image-66c8cf2c

思路分析

分三类情况讨论 魏国赢 蜀国赢 吴国赢

针对一种情况来说

魏国赢的话 应该是要a>b+c 转变成a-b-c>0

那么实际的每个事件也可以变形成对魏国赢的贡献值

image-d8676d85

显然这种情况下魏国是不可能赢的 三个事件对魏国获胜都是负贡献

考虑蜀国赢的情况

image-2bc437e9

显然 选择1，2事件可以让蜀国获胜

要选择尽可能多的事件让某国获胜

实际上就是在这些事件中选尽可能多的数 使得其总和大于0

那么贪心策略是 优先选择贡献较多的事件

那么可以把这些事件按降序排序

累加和应该会呈现一个这样的先升后降的趋势

image-4b000d48

我们要找到那个使得总和变成负前的最后一个事件是什么

它就是让某国获胜尽可能可以选到的最多的事件

这样做三遍 对每个国家都做一次 再在其中取个max就是最终答案

这个求得第一次变负的时候 可以联想到用前缀和 但是试了一下 确实是负优化 原本也就是一层循环用个sum累加 用前缀和也是一层循环 反而还加了一个LL数组

代码实现

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=100010;

int a[N],b[N],c[N],w[N];

int n;

int work(int x[],int y[],int z[])

{

    for(int i=1;i<=n;i++)

        w[i]=x[i]-y[i]-z[i];

    sort(w+1,w+n+1,greater<int>());

    int res=-1;

    LL sum=0;

    for(int i=1;i<=n;i++){

        sum+=w[i];

        if(sum>0)

            res=i;

        else

            break;

    }

    return res;

}

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++)

        cin>>a[i];

    for(int i=1;i<=n;i++)

        cin>>b[i];

    for(int i=1;i<=n;i++)

        cin>>c[i];

    int res=max({work(a,b,c),work(b,a,c),work(c,a,b)});

    cout<<res;

    return 0;

}

同类题型

视频讲解

⬅️ 哈夫曼模型 🏠 00-刷题理模型 ➡️ 乘积最大